翻訳と辞書 Words near each other ・ Parijata ・ Parijata yoga ・ Parijatapaharanamu ・ Parijatha ・ Parijatha Vaneswarar Temple ・ Parijatham ・ Parijnanashram ・ Parijnanashram I ・ Parijnanashram II ・ Parijnanashram III ・ Parika ・ Parika Nature Reserve ・ Parikan ・ Parikedun ・ Parikh ・ Parikh's theorem ・ Parikhan ・ Parikh–Doering oxidation ・ Parikia ・ Parikimys ・ Parikino ・ Parikipandla Narahari ・ Parikkala ・ Parikkalpattu ・ Parikrama ・ Parikrama (band) ・ Parikrama (company) ・ Parikrama (disambiguation) ・ Parikrama education ・ Parikrma Humanity Foundation Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Parikh's theorem ： ウィキペディア英語版 Parikh's theorem Parikh's theorem in theoretical computer science says that if one looks only at the relative number of occurrences of terminal symbols in a context-free language, without regard to their order, then the language is indistinguishable from a regular language. It is useful for deciding whether or not a string with a given number of some terminals is accepted by a context-free grammar.〔(【引用サイトリンク】title=Parikh's theorem )〕 It was first proved by Rohit Parikh in 1961 and republished in 1966. ==Definitions and formal statement== Let $\backslash Sigma=\backslash$ be an alphabet. The ''Parikh vector'' of a word is defined as the function $p:\backslash Sigma^$ *\to\mathbb^k, given by〔 $p(w)=(|w|\_,\; |w|\_,\; \backslash ldots,\; |w|\_)$, where $|w|\_$ denotes the number of occurrences of the letter $a\_i$ in the word $w$. A subset of $\backslash mathbb^k$ is said to be ''linear'' if it is of the form $u\_0+\backslash langle\; u\_1,\backslash ldots,u\_m\backslash rangle=\backslash$ for some vectors $u\_0,\backslash ldots,u\_m$. A subset of $\backslash mathbb^k$ is said to be ''semi-linear'' if it is a union of finitely many linear subsets. The formal statement of Parikh's theorem is as follows. Let $L$ be a context-free language. Let $P(L)$ be the set of Parikh vectors of words in $L$, that is, $P(L)\; =\; \backslash$. Then $P(L)$ is a semi-linear set. If $S$ is any semi-linear set, the language of words whose Parikh vectors are in $S$ is a regular language. Thus, if one considers two languages to be ''commutatively equivalent'' if they have the same set of Parikh vectors, then every context-free language is commutatively equivalent to some regular language. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Parikh's theorem」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.